home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / DJLSR106.ARJ / MALLOC.C < prev    next >
C/C++ Source or Header  |  1992-03-02  |  11KB  |  410 lines
  1. /*
  2.  * Copyright (c) 1983 Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms are permitted
  6.  * provided that: (1) source distributions retain this entire copyright
  7.  * notice and comment, and (2) distributions including binaries display
  8.  * the following acknowledgement:  ``This product includes software
  9.  * developed by the University of California, Berkeley and its contributors''
  10.  * in the documentation or other materials provided with the distribution
  11.  * and in all advertising materials mentioning features or use of this
  12.  * software. Neither the name of the University nor the names of its
  13.  * contributors may be used to endorse or promote products derived
  14.  * from this software without specific prior written permission.
  15.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  16.  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  17.  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  18.  */
  19.  
  20. #if defined(LIBC_SCCS) && !defined(lint)
  21. static char sccsid[] = "@(#)malloc.c    5.9 (Berkeley) 6/1/90";
  22. #endif /* LIBC_SCCS and not lint */
  23.  
  24. /*
  25.  * malloc.c (Caltech) 2/21/82
  26.  * Chris Kingsley, kingsley@cit-20.
  27.  *
  28.  * This is a very fast storage allocator.  It allocates blocks of a small 
  29.  * number of different sizes, and keeps free lists of each size.  Blocks that
  30.  * don't exactly fit are passed up to the next larger size.  In this 
  31.  * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long.
  32.  * This is designed for use in a virtual memory environment.
  33.  */
  34.  
  35. #include <sys/types.h>
  36.  
  37. #define    NULL 0
  38.  
  39. /*
  40.  * The overhead on a block is at least 4 bytes.  When free, this space
  41.  * contains a pointer to the next free block, and the bottom two bits must
  42.  * be zero.  When in use, the first byte is set to MAGIC, and the second
  43.  * byte is the size index.  The remaining bytes are for alignment.
  44.  * If range checking is enabled then a second word holds the size of the
  45.  * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC).
  46.  * The order of elements is critical: ov_magic must overlay the low order
  47.  * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern.
  48.  */
  49. union    overhead {
  50.     union    overhead *ov_next;    /* when free */
  51.     struct {
  52.         u_char    ovu_magic;    /* magic number */
  53.         u_char    ovu_index;    /* bucket # */
  54. #ifdef RCHECK
  55.         u_short    ovu_rmagic;    /* range magic number */
  56.         u_int    ovu_size;    /* actual block size */
  57. #endif
  58.     } ovu;
  59. #define    ov_magic    ovu.ovu_magic
  60. #define    ov_index    ovu.ovu_index
  61. #define    ov_rmagic    ovu.ovu_rmagic
  62. #define    ov_size        ovu.ovu_size
  63. };
  64.  
  65. #define    MAGIC        0xef        /* magic # on accounting info */
  66. #define RMAGIC        0x5555        /* magic # on range info */
  67.  
  68. #ifdef RCHECK
  69. #define    RSLOP        sizeof (u_short)
  70. #else
  71. #define    RSLOP        0
  72. #endif
  73.  
  74. /*
  75.  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
  76.  * smallest allocatable block is 8 bytes.  The overhead information
  77.  * precedes the data area returned to the user.
  78.  */
  79. #define    NBUCKETS 30
  80. static    union overhead *nextf[NBUCKETS];
  81. extern    char *sbrk();
  82.  
  83. static    int pagesz;            /* page size */
  84. static    int pagebucket;            /* page size bucket */
  85.  
  86. #ifdef MSTATS
  87. /*
  88.  * nmalloc[i] is the difference between the number of mallocs and frees
  89.  * for a given block size.
  90.  */
  91. static    u_int nmalloc[NBUCKETS];
  92. #include <stdio.h>
  93. #endif
  94.  
  95. #if defined(DEBUG) || defined(RCHECK)
  96. #define    ASSERT(p)   if (!(p)) botch("p")
  97. #include <stdio.h>
  98. static
  99. botch(s)
  100.     char *s;
  101. {
  102.     fprintf(stderr, "\r\nassertion botched: %s\r\n", s);
  103.      (void) fflush(stderr);        /* just in case user buffered it */
  104.     abort();
  105. }
  106. #else
  107. #define    ASSERT(p)
  108. #endif
  109.  
  110. char *
  111. malloc(nbytes)
  112.     unsigned nbytes;
  113. {
  114.       register union overhead *op;
  115.       register int bucket, n;
  116.     register unsigned amt;
  117.  
  118.     /*
  119.      * First time malloc is called, setup page size and
  120.      * align break pointer so all data will be page aligned.
  121.      */
  122.     if (pagesz == 0) {
  123.         pagesz = n = getpagesize();
  124.         op = (union overhead *)sbrk(0);
  125.           n = n - sizeof (*op) - ((int)op & (n - 1));
  126.         if (n < 0)
  127.             n += pagesz;
  128.           if (n) {
  129.               if (sbrk(n) == (char *)-1)
  130.                 return (NULL);
  131.         }
  132.         bucket = 0;
  133.         amt = 8;
  134.         while (pagesz > amt) {
  135.             amt <<= 1;
  136.             bucket++;
  137.         }
  138.         pagebucket = bucket;
  139.     }
  140.     /*
  141.      * Convert amount of memory requested into closest block size
  142.      * stored in hash buckets which satisfies request.
  143.      * Account for space used per block for accounting.
  144.      */
  145.     if (nbytes <= (n = pagesz - sizeof (*op) - RSLOP)) {
  146. #ifndef RCHECK
  147.         amt = 8;    /* size of first bucket */
  148.         bucket = 0;
  149. #else
  150.         amt = 16;    /* size of first bucket */
  151.         bucket = 1;
  152. #endif
  153.         n = -(sizeof (*op) + RSLOP);
  154.     } else {
  155.         amt = pagesz;
  156.         bucket = pagebucket;
  157.     }
  158.     while (nbytes > amt + n) {
  159.         amt <<= 1;
  160.         if (amt == 0)
  161.             return (NULL);
  162.         bucket++;
  163.     }
  164.     /*
  165.      * If nothing in hash bucket right now,
  166.      * request more memory from the system.
  167.      */
  168.       if ((op = nextf[bucket]) == NULL) {
  169.           morecore(bucket);
  170.           if ((op = nextf[bucket]) == NULL)
  171.               return (NULL);
  172.     }
  173.     /* remove from linked list */
  174.       nextf[bucket] = op->ov_next;
  175.     op->ov_magic = MAGIC;
  176.     op->ov_index = bucket;
  177. #ifdef MSTATS
  178.       nmalloc[bucket]++;
  179. #endif
  180. #ifdef RCHECK
  181.     /*
  182.      * Record allocated size of block and
  183.      * bound space with magic numbers.
  184.      */
  185.     op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
  186.     op->ov_rmagic = RMAGIC;
  187.       *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
  188. #endif
  189.       return ((char *)(op + 1));
  190. }
  191.  
  192. char *
  193. calloc(size,nelem) /* added by DJ Delorie */
  194. unsigned size;
  195. unsigned nelem;
  196. {
  197.   char *rv = malloc(size*nelem);
  198.   if (rv)
  199.     bzero(rv, size*nelem);
  200.   return rv;
  201. }
  202.  
  203. /*
  204.  * Allocate more memory to the indicated bucket.
  205.  */
  206. morecore(bucket)
  207.     int bucket;
  208. {
  209.       register union overhead *op;
  210.     register int sz;        /* size of desired block */
  211.       int amt;            /* amount to allocate */
  212.       int nblks;            /* how many blocks we get */
  213.  
  214.     /*
  215.      * sbrk_size <= 0 only for big, FLUFFY, requests (about
  216.      * 2^30 bytes on a VAX, I think) or for a negative arg.
  217.      */
  218.     sz = 1 << (bucket + 3);
  219. #ifdef DEBUG
  220.     ASSERT(sz > 0);
  221. #else
  222.     if (sz <= 0)
  223.         return;
  224. #endif
  225.     if (sz < pagesz) {
  226.         amt = pagesz;
  227.           nblks = amt / sz;
  228.     } else {
  229.         amt = sz + pagesz;
  230.         nblks = 1;
  231.     }
  232.     op = (union overhead *)sbrk(amt);
  233.     /* no more room! */
  234.       if ((int)op == -1)
  235.           return;
  236.     /*
  237.      * Add new memory allocated to that on
  238.      * free list for this hash bucket.
  239.      */
  240.       nextf[bucket] = op;
  241.       while (--nblks > 0) {
  242.         op->ov_next = (union overhead *)((caddr_t)op + sz);
  243.         op = (union overhead *)((caddr_t)op + sz);
  244.       }
  245. }
  246.  
  247. free(cp)
  248.     char *cp;
  249. {   
  250.       register int size;
  251.     register union overhead *op;
  252.  
  253.       if (cp == NULL)
  254.           return;
  255.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  256. #ifdef DEBUG
  257.       ASSERT(op->ov_magic == MAGIC);        /* make sure it was in use */
  258. #else
  259.     if (op->ov_magic != MAGIC)
  260.         return;                /* sanity */
  261. #endif
  262. #ifdef RCHECK
  263.       ASSERT(op->ov_rmagic == RMAGIC);
  264.     ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC);
  265. #endif
  266.       size = op->ov_index;
  267.       ASSERT(size < NBUCKETS);
  268.     op->ov_next = nextf[size];    /* also clobbers ov_magic */
  269.       nextf[size] = op;
  270. #ifdef MSTATS
  271.       nmalloc[size]--;
  272. #endif
  273. }
  274.  
  275. /*
  276.  * When a program attempts "storage compaction" as mentioned in the
  277.  * old malloc man page, it realloc's an already freed block.  Usually
  278.  * this is the last block it freed; occasionally it might be farther
  279.  * back.  We have to search all the free lists for the block in order
  280.  * to determine its bucket: 1st we make one pass thru the lists
  281.  * checking only the first block in each; if that fails we search
  282.  * ``realloc_srchlen'' blocks in each list for a match (the variable
  283.  * is extern so the caller can modify it).  If that fails we just copy
  284.  * however many bytes was given to realloc() and hope it's not huge.
  285.  */
  286. int realloc_srchlen = 4;    /* 4 should be plenty, -1 =>'s whole list */
  287.  
  288. char *
  289. realloc(cp, nbytes)
  290.     char *cp; 
  291.     unsigned nbytes;
  292. {   
  293.       register u_int onb;
  294.     register int i;
  295.     union overhead *op;
  296.       char *res;
  297.     int was_alloced = 0;
  298.  
  299.       if (cp == NULL)
  300.           return (malloc(nbytes));
  301.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  302.     if (op->ov_magic == MAGIC) {
  303.         was_alloced++;
  304.         i = op->ov_index;
  305.     } else {
  306.         /*
  307.          * Already free, doing "compaction".
  308.          *
  309.          * Search for the old block of memory on the
  310.          * free list.  First, check the most common
  311.          * case (last element free'd), then (this failing)
  312.          * the last ``realloc_srchlen'' items free'd.
  313.          * If all lookups fail, then assume the size of
  314.          * the memory block being realloc'd is the
  315.          * largest possible (so that all "nbytes" of new
  316.          * memory are copied into).  Note that this could cause
  317.          * a memory fault if the old area was tiny, and the moon
  318.          * is gibbous.  However, that is very unlikely.
  319.          */
  320.         if ((i = findbucket(op, 1)) < 0 &&
  321.             (i = findbucket(op, realloc_srchlen)) < 0)
  322.             i = NBUCKETS;
  323.     }
  324.     onb = 1 << (i + 3);
  325.     if (onb < pagesz)
  326.         onb -= sizeof (*op) + RSLOP;
  327.     else
  328.         onb += pagesz - sizeof (*op) - RSLOP;
  329.     /* avoid the copy if same size block */
  330.     if (was_alloced) {
  331.         if (i) {
  332.             i = 1 << (i + 2);
  333.             if (i < pagesz)
  334.                 i -= sizeof (*op) + RSLOP;
  335.             else
  336.                 i += pagesz - sizeof (*op) - RSLOP;
  337.         }
  338.         if (nbytes <= onb && nbytes > i) {
  339. #ifdef RCHECK
  340.             op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
  341.             *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
  342. #endif
  343.             return(cp);
  344.         } else
  345.             free(cp);
  346.     }
  347.       if ((res = malloc(nbytes)) == NULL)
  348.           return (NULL);
  349.       if (cp != res)        /* common optimization if "compacting" */
  350.         bcopy(cp, res, (nbytes < onb) ? nbytes : onb);
  351.       return (res);
  352. }
  353.  
  354. /*
  355.  * Search ``srchlen'' elements of each free list for a block whose
  356.  * header starts at ``freep''.  If srchlen is -1 search the whole list.
  357.  * Return bucket number, or -1 if not found.
  358.  */
  359. static
  360. findbucket(freep, srchlen)
  361.     union overhead *freep;
  362.     int srchlen;
  363. {
  364.     register union overhead *p;
  365.     register int i, j;
  366.  
  367.     for (i = 0; i < NBUCKETS; i++) {
  368.         j = 0;
  369.         for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
  370.             if (p == freep)
  371.                 return (i);
  372.             j++;
  373.         }
  374.     }
  375.     return (-1);
  376. }
  377.  
  378. #ifdef MSTATS
  379. /*
  380.  * mstats - print out statistics about malloc
  381.  * 
  382.  * Prints two lines of numbers, one showing the length of the free list
  383.  * for each size category, the second showing the number of mallocs -
  384.  * frees for each size category.
  385.  */
  386. mstats(s)
  387.     char *s;
  388. {
  389.       register int i, j;
  390.       register union overhead *p;
  391.       int totfree = 0,
  392.       totused = 0;
  393.  
  394.       fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s);
  395.       for (i = 0; i < NBUCKETS; i++) {
  396.           for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
  397.               ;
  398.           fprintf(stderr, " %d", j);
  399.           totfree += j * (1 << (i + 3));
  400.       }
  401.       fprintf(stderr, "\nused:\t");
  402.       for (i = 0; i < NBUCKETS; i++) {
  403.           fprintf(stderr, " %d", nmalloc[i]);
  404.           totused += nmalloc[i] * (1 << (i + 3));
  405.       }
  406.       fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n",
  407.         totused, totfree);
  408. }
  409. #endif
  410.